package list;

public class ReverseList {
    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);

        Node head2 = reverse(head);

        Node n = head2;
        while (n != null) {
            System.out.println(n.value);
            n = n.next;
        }
    }

    /*
    翻转链表思路： 从头部节点开始，一个节点一个节点地拆出来，重新反向连接

    1. 变量current,先引用头部节点
    2. 变量next,表示新链表中的下一个节点，开始是null
    3. 进入循环，循环条件：current!=null
    4. 定义tmp变量表示当前节点的下一个节点
    5. current的下一个，引用next
    6. 修改next变量，引用current节点
    7. 修改current变量，引用tmp节点
    8. 循环结束后，next引用的节点，就是新的头部节点，直接返回next
     */

    private static Node reverse(Node head) {
        if (head == null || head.next == null) {
            return head;
        }

        Node current = head;
        Node next = null;
        while (current != null) {
            Node tmp = current.next;
            current.next = next;
            next = current;
            current = tmp;
        }
        return next;
    }

    static class Node {
        int value;
        Node prev;
        Node next;

        Node(int value) {
            this.value = value;
        }
    }
}
